#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef struct ListNode
{
    int val;
    struct ListNode* next;
}ListNode;
 
ListNode* GetIntersectionNode(ListNode* headA, ListNode* headB)
{
    ListNode* tailA = headA;
    ListNode* tailB = headB;
    int lenA = 1;
    int lenB = 1;
    while (tailA)
    {
        tailA = tailA->next;
        lenA++;
    }
    while (tailB)
    {
        tailB = tailB->next;
        lenB++;
    }
    if (tailA != tailB)
    {
        return NULL;
    }
    int gap = abs(lenA - lenB);
    ListNode* longlist = headA;
    ListNode* shortlsit = headB;
    if (lenA < lenB)
    {
        longlist = headB;
        shortlsit = headA;
    }
    while (gap--)
    {
        longlist = longlist->next;
    }
    while (longlist != shortlsit)
    {
        longlist = longlist->next;
        shortlsit = shortlsit->next;
    }
    return longlist;
}

ListNode* CreateList(int* num, int sz)
{
    ListNode* head = NULL;
    ListNode* tail = NULL;
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
        if (newnode == NULL)
        {
            perror("malloc:");
            return NULL;
        }
        newnode->val = num[i];
        newnode->next = NULL;
        if (head == NULL)
        {
            head = tail = newnode;
        }
        else
        {
            tail->next = newnode;
            tail = tail->next;
        }
    }
    return head;
}

LinkList(ListNode** pphead, ListNode* phead)
{
    assert(pphead);
    assert(phead);
    ListNode* cur = *pphead;
    while (cur->next != NULL)
    {
        cur = cur->next;
    }
    cur->next = phead;
}

void PrintList(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead;
    while (cur != NULL)
    {
        printf("%d -> ", cur->val);
        cur = cur->next;
    }
    printf("NULL\n");
}
void DestroyList(ListNode** pphead)
{
    assert(pphead);
    ListNode* cur = *pphead;
    while ((*pphead) != NULL)
    {
        *pphead = (*pphead)->next;
        free(cur);
        cur = *pphead;
    }
}

int main()
{
    int arr1[] = { 4,1 };
    int arr2[] = { 5,6,1 };
    int arr3[] = { 8,4,5 };
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    int size3 = sizeof(arr3) / sizeof(arr3[0]);
    ListNode* phead1 = CreateList(arr1, size1);
    ListNode* phead2 = CreateList(arr2, size2);
    ListNode* phead3 = CreateList(arr3, size3);
    LinkList(&phead1, phead3);
    LinkList(&phead2, phead3);
    PrintList(phead1);
    PrintList(phead2);
    ListNode* cur = GetIntersectionNode(phead1, phead2);
    printf("Intersected at '%d'\n", cur->val);
    return 0;
}